package com.zzg.algorithm.prim;

import com.zzg.algorithm.prim.entity.MGraph;
import com.zzg.algorithm.prim.tree.MinTree;

/**
 * @Author zhengzg
 * @Date 2022-10-10
 * @Version v1.0
 * 普利姆算法：修路问题
 * 1) 有胜利乡有 7 个村庄(A, B, C, D, E, F, G) ，现在需要修路把 7 个村庄连通
 * 2) 各个村庄的距离用边线表示(权) ，比如 A – B 距离 5 公里
 * 3) 问：如何修路保证各个村庄都能连通，并且总的修建公路总里程最短?
 */
public class PrimAlgorithm {
    public static void main(String[] args) {
        char[] data = new char[]{'A', 'B', 'C', 'D', 'E', 'F', 'G'};
        int verxs = data.length;
        // 邻接矩阵的关系使用二维数组
        int[][] weight = new int[][]{
                {10000, 5, 7, 10000, 10000, 10000, 2},
                {5, 10000, 10000, 9, 10000, 10000, 3},
                {7, 10000, 10000, 10000, 8, 10000, 10000},
                {10000, 9, 10000, 10000, 10000, 4, 10000},
                {10000, 10000, 8, 10000, 10000, 5, 4},
                {10000, 10000, 10000, 4, 5, 10000, 6},
                {2, 3, 10000, 10000, 4, 6, 10000},};

        MGraph graph = new MGraph(verxs);
        MinTree minTree = new MinTree();
        minTree.createGraph(graph, verxs, data, weight);
        minTree.showGraph(graph);
        minTree.prim(graph, 1);

    }
}
